#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>

#define FILEIO

typedef int Type;
#define max 5


//All leaves have same depth, which is the tree's height h
//B tree degree 2t - 1 = max, t = (max + 1)/2;

typedef struct btree
{
  // The number of key inside the node.
  // n <= max
  Type n;
  /*
    x.key1<x.key2<x.key3
   */
  Type key[max];
  /*
    pointer point to child node with seperated
    note: the leaf didn't have any child. so this pointer array is NULL.
   */
  struct btree* child[max + 1];
  /*
    To mark it whether it is leaf or not.
   */
  int isLeaf;
  
}*BTree,Tree;

void disk_read(BTree b)
{
  
}

BTree xalloc()
{
  BTree p = (BTree)malloc(sizeof(Tree));

  if(p == NULL) 
      return 0;

  return p;
}

void btree_create()
{
  
}

BTree btree_search(BTree x,Type k)
{
	int i=1;

	while(i<=x->n && k>=x->key[i])
		i++;

	if(i<=x->n && k==x->key[i])
		return x;

	// if can not search k in the x
	// Try to search child node or if it is leaf node, return nil
	if(x->isLeaf)
		return NULL;
	else
		return btree_search(x->child[i],k);
}

void btree_split_child(BTree x,Type i,BTree y)
{
	BTree z = xalloc();

	z->isLeaf = y->isLeaf;

	int t = (max+1)/2;


}

int btree_main() 
{ 

#ifdef FILEIO
  freopen("in.txt","r",stdin); 
  freopen("out.txt","w",stdout); 
#endif



#ifdef FILEIO
  fclose(stdin);
  fclose(stdout);
#endif
  
  return 0; 
} 
